Finding minimum cost or “shortest” paths, generally optimal paths or “most likely to succeed” paths, is important in many practical transportation and communication applications. The problem is to find a route from a source to a destination under certain constraints. For example, a best geographical route to the airport before a departure time, a best route on the drive home before running out of fuel, or a best route in a network to send packets with minimum delay.
The invention is concerned with paths that can be modeled as a stochastic network (graph). A stochastic network includes nodes connected by edges. The edges represent the individual paths that can form a potential optimal route, and the nodes are intermediate points where alternative paths can be selected for a particular route. In a stochastic network, a cost of traversing an edge (path) is drawn randomly according to a probability distribution associated with the edge. Typically, the cost distribution represents a ‘length’ of the edge, or the travel time to traverse the edge. This is how the real world works.
Because it is difficult to define the meaning of stochastic shortest paths, it is also difficult to formalize the problem. When the edges that model the paths are modeled by probability distributions, the shortest paths could determine an average, minimize a combination of mean and variance, or minimizing some other specified criterion. In addition, the shortest paths can be found adaptively or non-adaptively. Adaptive methods are most common, perhaps because a non-adaptive minimization of the expected path length trivially reduces to a deterministic shortest path problem.
Most prior art methods minimize an expected length of paths from the source to the destination, or a combination of expected lengths and expected costs such as bicriterion problems, J. Mote, I. Murthy, and D. Olson, “A parametric approach to solving bicriterion shortest path problems,” European Journal of Operational Research, 53:81-92, 1991, and S. Pallottino and M. G. Scutella, “Shortest path processes in transportation models: Classical and innovative aspects,” Technical Report TR-97-06, Universita di Pisa Dipartimento di Informatica, 1997.
Some methods optimize a non-linear function of the path length. Other methods define a decision-theoretic framework, R. P. Loui, “Optimal paths in graphs with stochastic or multi-dimensional weights,” Communications of the ACM, 26:670-676, 1983. There, the optimal path maximizes an expected utility for a class of monotonically increasing utility functions.
An adaptive method for finding shortest paths that maximizes the probability of arriving before the deadline is described by Y. Fan, R. Kalaba, and I. J. E. Moore, “Arriving on time,” Journal of Optimization Theory and Applications, Vol. 127, No. 3, pp. 485-496, December 2005. Formulations of this type with a nonlinear objective function, though perhaps most useful in practice, are few, because the hardness of the problem arises and accumulates from many levels, e.g., combinatorial, distributional, analytic, functional, to list a few. For example, in the absence of randomness, the combinatorial nature of the problem may be hard to approximate. In the absence of a graph structure, the objective function may be difficult to optimize.
A stochastic shortest paths model can effectively reduce the above difficulties.
Most prior art methods that operates on stochastic shortest paths use adaptive processes. There, the selection of the best next path is based on information about realized edge lengths so far. Most of the adaptive methods focus on minimizing expected length; few consider minimizing a non-linear function of the length and only give approximate heuristic processes.
The most relative method is that of Loui. Loui considers a general utility function of the path length which is monotone and non-decreasing, and proves that the expected utility becomes separable into the edge lengths only when the utility function is linear or exponential. In that case, the path that maximizes the expected utility can be found via traditional shortest path process. For general utility functions, Loui describes a process based on a certain enumeration of paths.
Mirchandani and Soroush give exponential processes and heuristics for quadratic utility functions, P. Mirchandani and H. Soroush, “Optimal paths in probabilistic networks: a case with temporary preferences,” Computers and Operations Research, 12(4):365-381, 1985. For non-monotone utility functions that use penalties, Nikolova et al., give hardness results and pseudo-polynomial processes, E. Nikolova, M. Brand, and D. R. Karger, “Optimal route planning under uncertainty,” Proceedings of International Conference on Automated Planning and Scheduling, 2006.